package hard;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class T6378 {
    List<Integer>[] lists;
    int[] cnt;
    int end;
    int[][] dp;
    int[] price;

    public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {

        cnt = new int[n];
        lists = new ArrayList[n];
        Arrays.setAll(lists, (e) -> new ArrayList<>());
        for (int[] edge : edges) {
            lists[edge[0]].add(edge[1]);
            lists[edge[1]].add(edge[0]);
        }
        for (int[] trip : trips) {
            end = trip[1];
            path(-1, trip[0]);
        }


        for (int i = 0; i < n; i++) {
            price[i] *= cnt[i];
        }
        this.price = price;
        dp = new int[2][n];
        Arrays.fill(dp[0], -1);
        Arrays.fill(dp[1], -1);
        return dfs(-1,0, false);
    }

    public boolean path(int left, int start) {
        System.out.println(start);
        if (start == end) {
            cnt[start]++;
            return true;
        }
        if (lists[start].isEmpty()) return false;
        for (int next : lists[start]) {
            if (next != left && path(start,next)) {
                cnt[start]++;
                return true;
            }
        }
        return false;
    }

    public int dfs(int grand,int father, boolean isLimit) {
        if (dp[isLimit ? 1 : 0][father] != -1) {
            return dp[isLimit ? 1 : 0][father];
        }
        int min = price[father];
        for (int next : lists[father]) {
            if (next!=grand)min += dfs(father,next, false);
        }
        if (!isLimit) {
            int sum = price[father] / 2;
            for (int next : lists[father]) {
                if (next!=grand)sum += dfs(father,next, true);
            }
            min = Math.min(min, sum);
        }
        dp[isLimit ? 1 : 0][father] = min;
        return min;
    }


}
